Corelab Seminar
2017-2018
Ioannis Kokkinis
Reachability and Expectation in Sequential Gossiping
Abstract.
A gossip protocol aims at arriving, by means of point-to-point communications (or telephone calls), at a situation in which every agent knows all the information initially present in the network. If it is impossible to have more than one call at the same time, the protocol is called sequential. In this talk we study 5 sequential gossip protocols. We model the protocols as discrete time Markov chains, with the aim of answering two questions: what knowledge distributions are reached during the execution of the protocols and what is the expected duration of the protocols. For the former question we conclude, by doing an exhaustive search, that the 5 protocols reach different knowledge distributions whereas for the latter question we present an algorithm that computes the exact value of the expected duration (for a small number of agents) and we show how bounds for the asymptotic behaviour of the expected duration can be computed.